package problem542;

import java.util.LinkedList;
import java.util.Queue;

//542.01矩阵
//https://leetcode.cn/problems/01-matrix/

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        Queue<int[]> queue = new LinkedList<>();
        int n = mat.length, m = mat[0].length;
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(mat[i][j] == 0) {
                    queue.add(new int[]{i, j});
                }
            }
        }

        boolean[][] st = new boolean[n][m];
        int[] xx = {1,-1,0,0};
        int[] yy = {0,0,1,-1};
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size -- > 0) {
                int[] t = queue.poll();
                int x = t[0], y = t[1];
                for(int i = 0; i<4; i++) {
                    int dx = x + xx[i];
                    int dy = y + yy[i];
                    if(dx >= 0 && dx < n && dy >= 0 && dy < m && mat[dx][dy] != 0 && !st[dx][dy]) {
                        mat[dx][dy] = mat[x][y] + 1;
                        st[dx][dy] = true;
                        queue.add(new int[]{dx, dy});
                    }
                }
            }
        }
        return mat;
    }
}








